package a;

import java.util.HashMap;
import java.util.Map;

class DouNode{
    int key,val;
    DouNode left,right;
    DouNode(int k,int v){key=k;val=v;}
}
class LRUCache {
    int cS,mS=0;
    DouNode d1,d2;
    Map<Integer,DouNode> map = new HashMap<>();
    public LRUCache(int capacity) {
        mS=capacity;
        d1 = new DouNode(-1,-1);d2 = new DouNode(-1,-1); d1.right=d2;d2.left=d1;
    }

    /*
        工具参数都用DN node
        删中间、最右加
    */
    public void delMid(DouNode c){
        cS--;
        DouNode lf = c.left, rt=c.right;  lf.right=rt;rt.left=lf;
    }
    public void addRightLast(DouNode c){
        cS++;
        DouNode last = d2.left;
        //不放心
        last.right=c;c.left=last;
        c.right=d2;d2.left=c;
    }


    /*
        拿Node 链表 map
    */
    public void put(int key, int value) {
        //有key，不+1所以不会满
        if(map.containsKey(key)){
            //-中
            DouNode m = map.get(key); delMid(m); map.remove(key);
            //+右
            DouNode nN = new DouNode(key, value); addRightLast(nN); map.put(key,nN);
        }
        //无key，满了可能顶出去
        else{
            //不满
            if(cS<mS){
                //+右
                DouNode nN = new DouNode(key, value); addRightLast(nN); map.put(key,nN);
            }
            //满了
            else{
                //-左
                DouNode l = d1.right; delMid(l); map.remove(l.key);//找key:node.点
                //+右
                DouNode nN = new DouNode(key, value); addRightLast(nN); map.put(key,nN);
            }
        }
    }
    public int get(int key) {
        //先不存在
        if(!map.containsKey(key))return -1;

        //-中
        DouNode m = map.get(key); delMid(m); map.remove(key);
        //+右
        DouNode nN = m; addRightLast(nN); map.put(key,nN);
        return m.val;
    }
}
